Reshape the matrix

Time: O(M N); Space: O(M * N); easy

In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data. You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.

The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the ‘reshape’ operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

Example 1:

Input: nums = [[1,2], [3,4]], r = 1, c = 4

Output: [[1,2,3,4]]

Explanation:

  • The row-traversing of nums is [1,2,3,4].

  • The new reshaped matrix is a 1x4 matrix,

  • fill it row by row by using the previous list.

Example 2:

Input: nums = [[1,2],[3,4]], r = 2, c = 4

Output: [[1,2],[3,4]]

Explanation:

  • There is no way to reshape a 2x2 matrix to a 2x4 matrix.

  • So output the original matrix.

Notes:

  • The height and width of the given matrix is in range [1, 100].

  • The given r and c are all positive.

Hints:

  1. Do you know how 2d matrix is stored in 1d memory? Try to map 2-dimensions into one.

  2. M[i][j] = M[n*i+j], where n is the number of cols. This is the one way of converting 2-d indices into one 1-d index. Now, how will you convert 1-d index into 2-d indices?

  3. Try to use division and modulus to convert 1-d index into 2-d indices.

  4. M[i] => M[n/i][n%i] Will it result in right mapping? Take some example and check this formulae.

[3]:

class Solution1(object):
    def matrixReshape(self, nums, r, c):
        """
        :type nums: List[List[int]]
        :type r: int
        :type c: int
        :rtype: List[List[int]]
        """
        if not nums or r*c != len(nums) * len(nums[0]):
            return nums

        result = [[0 for _ in range(c)] for _ in range(r)]
        count = 0

        for i in range(len(nums)):
            for j in range(len(nums[0])):
                result[count // c][count % c] = nums[i][j]
                count += 1

        return result

[4]:

s = Solution1()
nums = [[1,2], [3,4]]
r = 1
c = 4
assert s.matrixReshape(nums, r, c) == [[1,2,3,4]]
nums = [[1,2],[3,4]]
r = 2
c = 4
assert s.matrixReshape(nums, r, c) == [[1,2],[3,4]]

[5]:

class Solution2(object):
    def matrixReshape(self, nums, r, c):
        """
        :type nums: List[List[int]]
        :type r: int
        :type c: int
        :rtype: List[List[int]]
        """
        matrix=[]
        one_row=[]
        for i in nums:
            for j in i:
                one_row.append(j)
        if r*c == len(one_row):
            for i in range(0,len(one_row),c):
                matrix.append(one_row[i:i+c])
            return matrix
        else:
            return nums

[6]:

s = Solution2()
nums = [[1,2], [3,4]]
r = 1
c = 4
assert s.matrixReshape(nums, r, c) == [[1,2,3,4]]
nums = [[1,2],[3,4]]
r = 2
c = 4
assert s.matrixReshape(nums, r, c) == [[1,2],[3,4]]